﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using ParserGenerator.Extensions;

namespace ParserGenerator.Collections
{
    [Serializable,
     DebuggerDisplay(DebugDisplay),
     DebuggerTypeProxy(typeof(Sequence<>.DebugView))]
    public abstract class Sequence<T>
        : IList<T>, IReadOnlyList<T>, IList
        , IEquatable<Sequence<T>>, IComparable<Sequence<T>>, IComparable
    {
        #region bst details
        [Serializable]
        internal sealed class Leaf : Sequence<T>
        {
            public static Sequence<T> Instance { get; } = new Leaf();

            private Leaf()
            {
            }
        }

        [Serializable]
        internal sealed class Node : Sequence<T>
        {
            public T Item { get; }
            public Sequence<T> Left { get; }
            public Sequence<T> Right { get; }
            public int Size { get; }

            internal Node(Sequence<T> left, T item, Sequence<T> right)
            {
                if (left == null)
                    throw new ArgumentNullException(nameof(left));
                if (right == null)
                    throw new ArgumentNullException(nameof(right));
                Item = item;
                Left = left;
                Right = right;
                Size = left.Count + right.Count + 1;
            }

            internal Node(T item)
            {
                Item = item;
                Left = Leaf.Instance;
                Right = Leaf.Instance;
                Size = 1;
            }
        }

        private const int TreeDelta = 3;
        private const int TreeRatio = 2;
        public int Count => SizeOf(this as Node);
        public int Length => SizeOf(this as Node);

        private Node GetNode(int index)
        {
            Node n = this as Node;
            while (n != null)
            {
                int c = n.Left.Count;
                int t = index.CompareTo(c);
                if (t < 0)
                    n = n.Left as Node;
                else if (t > 0)
                {
                    n = n.Right as Node;
                    index -= c + 1;
                }
                else
                {
                    return n;
                }
            }
            return null;
        }

        private static Sequence<T> BuildTree(int i, int m, IReadOnlyList<T> items)
        {
            if (m <= 0)
                return Leaf.Instance;
            int nl = m / 2;
            int nr = m - 1 - nl;
            int n = i + nl;
            Sequence<T> tl = BuildTree(i, nl, items);
            Sequence<T> tr = BuildTree(n + 1, nr, items);
            return new Node(tl, items[n], tr);
        }

        private static Sequence<T> BuildTree(int i, int m, IList<T> items)
        {
            if (m <= 0)
                return Leaf.Instance;
            int nl = m / 2;
            int nr = m - 1 - nl;
            int n = i + nl;
            Sequence<T> tl = BuildTree(i, nl, items);
            Sequence<T> tr = BuildTree(n + 1, nr, items);
            return new Node(tl, items[n], tr);
        }

        internal static Sequence<T> BuildTree(IEnumerable<T> collection)
        {
            var items = collection as IReadOnlyList<T>;
            if (items != null)
                return BuildTree(0, items.Count, items);
            var items2 = collection as IList<T>;
            if (items2 != null)
                return BuildTree(0, items2.Count, items2);
            return Leaf.Instance.AddRange(collection);
        }

        private static int SizeOf(Node node) => node != null ? node.Size : 0;

        private static Sequence<T> BalanceLeft(Sequence<T> left, T item, Sequence<T> right)
        {
            Node nl = left as Node;
            Node nr = right as Node;
            if (nr == null)
            {
                if (nl == null)
                    return new Node(item);
                Node nll = nl.Left as Node;
                Node nlr = nl.Right as Node;
                if (nlr == null)
                {
                    if (nll == null)
                        return new Node(nl, item, Leaf.Instance);
                    else
                        return new Node(nll, nl.Item, new Node(item));
                }
                if (nll == null)
                    return new Node(new Node(nl.Item), nlr.Item, new Node(item));
                if (nlr.Size < TreeRatio * nll.Size)
                    return new Node(nll, nl.Item, new Node(nlr, item, Leaf.Instance));
                Sequence<T> tl = new Node(nll, nl.Item, nlr.Left);
                Sequence<T> tr = new Node(nlr.Right, item, Leaf.Instance);
                return new Node(tl, nlr.Item, tr);
            }
            else
            {
                if (nl == null)
                    return new Node(Leaf.Instance, item, nr);
                if (nl.Size > TreeDelta * nr.Size)
                {
                    Node nll = nl.Left as Node;
                    Node nlr = nl.Right as Node;
                    if (nlr.Size < TreeRatio * nll.Size)
                        return new Node(nll, nl.Item, new Node(nlr, item, nr));
                    Sequence<T> tl = new Node(nll, nl.Item, nlr.Left);
                    Sequence<T> tr = new Node(nlr.Right, item, nr);
                    return new Node(tl, nlr.Item, tr);
                }
                return new Node(nl, item, nr);
            }
        }

        private static Sequence<T> BalanceRight(Sequence<T> left, T item, Sequence<T> right)
        {
            Node nl = left as Node;
            Node nr = right as Node;
            if (nl == null)
            {
                if (nr == null)
                    return new Node(item);
                Node nrl = nr.Left as Node;
                Node nrr = nr.Right as Node;
                if (nrl == null)
                {
                    if (nrr == null)
                        return new Node(Leaf.Instance, item, nr);
                    else
                        return new Node(new Node(item), nr.Item, nrr);
                }
                if (nrr == null)
                    return new Node(new Node(item), nrl.Item, new Node(nr.Item));
                if (nrl.Size < TreeRatio * nrr.Size)
                    return new Node(new Node(Leaf.Instance, item, nrl), nr.Item, nrr);
                Sequence<T> tl = new Node(Leaf.Instance, item, nrl.Left);
                Sequence<T> tr = new Node(nrl.Right, nr.Item, nrr);
                return new Node(tl, nrl.Item, tr);
            }
            else
            {
                if (nr == null)
                    return new Node(nl, item, Leaf.Instance);
                if (nr.Size > TreeDelta * nl.Size)
                {
                    Node nrl = nr.Left as Node;
                    Node nrr = nr.Right as Node;
                    if (nrl.Size < TreeRatio * nrr.Size)
                        return new Node(new Node(nl, item, nrl), nr.Item, nrr);
                    Sequence<T> tl = new Node(nl, item, nrl.Left);
                    Sequence<T> tr = new Node(nrl.Right, nr.Item, nrr);
                    return new Node(tl, nrl.Item, tr);
                }
                return new Node(nl, item, nr);
            }
        }

        private Sequence<T> InsertMinimum(T item)
        {
            Node n = this as Node;
            if (n == null)
                return new Node(item);
            return BalanceLeft(n.Left.InsertMinimum(item), n.Item, n.Right);
        }

        private Sequence<T> InsertMaximum(T item)
        {
            Node n = this as Node;
            if (n == null)
                return new Node(item);
            return BalanceRight(n.Left, n.Item, n.Right.InsertMaximum(item));
        }

        private Sequence<T> DeleteMinimum(out Node node)
        {
            Node n = this as Node;
            if (n.Left is Node)
                return BalanceRight(n.Left.DeleteMinimum(out node), n.Item, n.Right);
            node = n;
            return n.Right;
        }

        private Sequence<T> DeleteMaximum(out Node node)
        {
            Node n = this as Node;
            if (n.Right is Node)
                return BalanceLeft(n.Left, n.Item, n.Right.DeleteMaximum(out node));
            node = n;
            return n.Left;
        }

        private Sequence<T> AppendRange(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException(nameof(collection));
            if (collection == this)
                return Glue(this, this);
            Sequence<T> other = collection as Sequence<T>;
            if (other != null)
                return Concat(other);
            Sequence<T> list = this;
            foreach (T item in collection)
                list = list.InsertMaximum(item);
            return list;
        }

        private Sequence<T> PrependRange(IEnumerator<T> e)
        {
            if (e.MoveNext())
            {
                T item = e.Current;
                Sequence<T> list = PrependRange(e);
                return list.InsertMinimum(item);
            }
            return this;
        }

        private Sequence<T> PrependRange(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException(nameof(collection));
            if (collection == this)
                return Glue(this, this);
            Sequence<T> other = collection as Sequence<T>;
            if (other != null)
                return other.Concat(this);
            return PrependRange(collection.GetEnumerator());
        }

        private static Sequence<T> Glue(Sequence<T> left, Sequence<T> right)
        {
            Node nl = left as Node;
            Node nr = right as Node;
            if (nr == null)
                return left;
            if (nl == null)
                return right;
            if (nl.Size > nr.Size)
            {
                Node node;
                Sequence<T> t = nl.DeleteMaximum(out node);
                return BalanceRight(t, node.Item, nr);
            }
            else
            {
                Node node;
                Sequence<T> t = nr.DeleteMinimum(out node);
                return BalanceLeft(nl, node.Item, t);
            }
        }

        private static Sequence<T> Merge(Sequence<T> left, Sequence<T> right)
        {
            Node nl = left as Node;
            Node nr = right as Node;
            if (nr == null)
                return left;
            if (nl == null)
                return right;
            if (nl.Size > TreeDelta * nr.Size)
                return BalanceRight(nl.Left, nl.Item, Merge(nl.Right, nr));
            else if (nr.Size > TreeDelta * nl.Size)
                return BalanceLeft(Merge(nl, nr.Left), nr.Item, nr.Right);
            else
                return Glue(nl, nr);
        }

        private static Sequence<T> Link(Sequence<T> left, T value, Sequence<T> right)
        {
            Node nl = left as Node;
            Node nr = right as Node;
            if (nr == null)
                return left.InsertMaximum(value);
            if (nl == null)
                return right.InsertMinimum(value);
            if (nl.Size > TreeDelta * nr.Size)
                return BalanceRight(nl.Left, nl.Item, Link(nl.Right, value, nr));
            else if (nr.Size > TreeDelta * nl.Size)
                return BalanceLeft(Link(nl, value, nr.Left), nr.Item, nr.Right);
            else
                return new Node(nl, value, nr);
        }

        private static Sequence<T> Filter(Sequence<T> tree, Func<T, bool> predicate)
        {
            Node n = tree as Node;
            if (n == null)
                return Leaf.Instance;
            Sequence<T> tl = Filter(n.Left, predicate);
            Sequence<T> tr = Filter(n.Right, predicate);
            if (predicate(n.Item))
                return Link(tl, n.Item, tr);
            else
                return Merge(tl, tr);
        }

        public Sequence<T> Filter(Func<T, bool> predicate)
        {
            if (predicate == null)
                throw new ArgumentNullException(nameof(predicate));
            return Filter(this, predicate);
        }

        private static Tuple<Sequence<T>, Sequence<T>> Partition(Sequence<T> tree, Func<T, bool> predicate)
        {
            Node n = tree as Node;
            if (n == null)
                return Tuple.Create(Leaf.Instance, Leaf.Instance);
            Tuple<Sequence<T>, Sequence<T>> p = Partition(n.Left, predicate);
            Tuple<Sequence<T>, Sequence<T>> q = Partition(n.Right, predicate);
            if (predicate(n.Item))
                return Tuple.Create(Link(p.Item1, n.Item, q.Item1), Merge(p.Item2, q.Item2));
            else
                return Tuple.Create(Merge(p.Item1, q.Item1), Link(p.Item2, n.Item, q.Item2));
        }

        public Tuple<Sequence<T>, Sequence<T>> Partition(Func<T, bool> predicate)
        {
            if (predicate == null)
                throw new ArgumentNullException(nameof(predicate));
            return Partition(this, predicate);
        }

        public Sequence<TOutput> Map<TOutput>(Func<T, TOutput> mapper)
        {
            if (mapper == null)
                throw new ArgumentNullException(nameof(mapper));
            Sequence<TOutput> tree = Sequence<TOutput>.Leaf.Instance;
            foreach (T item in this)
                tree = tree.Add(mapper(item));
            return tree;
        }

        public Sequence<T> Concat(Sequence<T> other)
        {
            if (other == null)
                throw new ArgumentNullException(nameof(other));
            if (other == this)
                return Glue(this, this);
            return Merge(this, other);
        }

        public Sequence<T> ConcatWith(T separator, Sequence<T> other)
        {
            if (other == null)
                throw new ArgumentNullException(nameof(other));
            if (other == this)
                return new Node(this, separator, this);
            return Link(this, separator, other);
        }

        public Sequence<T> Join(IEnumerable<Sequence<T>> collection)
        {
            if (collection == null)
                throw new ArgumentNullException(nameof(collection));
            Sequence<T> list = this;
            foreach (Sequence<T> item in collection)
                list = list.Concat(item);
            return list;
        }

        public Sequence<T> JoinWith(T separator, IEnumerable<Sequence<T>> collection)
        {
            if (collection == null)
                throw new ArgumentNullException(nameof(collection));
            Sequence<T> list = this;
            foreach (Sequence<T> item in collection)
                list = list.ConcatWith(separator, item);
            return list;
        }

        public Sequence<T> Add(T item)
        {
            return InsertMaximum(item);
        }

        public Sequence<T> AddRange(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException(nameof(collection));
            return AppendRange(collection);
        }

        public Sequence<T> Clear()
        {
            return Leaf.Instance;
        }

        private Sequence<T> InsertItemAt(int index, T item)
        {
            Node n = this as Node;
            int c = n.Left.Count;
            int t = index.CompareTo(c);
            if (t < 0)
            {
                Sequence<T> tl = n.Left.InsertItemAt(index, item);
                return BalanceLeft(tl, n.Item, n.Right);
            }
            else if (t > 0)
            {
                Sequence<T> tr = n.Right.InsertItemAt(index - c - 1, item);
                return BalanceRight(n.Left, n.Item, tr);
            }
            else
            {
                Sequence<T> tr = n.Right.InsertMinimum(n.Item);
                return BalanceRight(n.Left, item, tr);
            }
        }

        public Sequence<T> Insert(int index, T item)
        {
            CheckListIndex(index, Count);
            if (index == Count)
                return InsertMaximum(item);
            if (index == 0)
                return InsertMinimum(item);
            return InsertItemAt(index, item);
        }

        public Sequence<T> InsertRange(int index, IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException(nameof(collection));
            CheckListIndex(index, Count);
            if (index == Count)
                return AppendRange(collection);
            if (index == 0)
                return PrependRange(collection);
            Sequence<T> list = this;
            foreach (T item in collection)
                list = list.Insert(index++, item);
            return list;
        }

        public Sequence<T> Remove(T item)
        {
            int index = IndexOf(item);
            if (index == -1)
                return this;
            return RemoveAt(index);
        }

        public Sequence<T> RemoveRange(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException(nameof(collection));
            if (collection == this)
                return Leaf.Instance;
            Sequence<T> list = this;
            foreach (T item in collection)
                list = list.Remove(item);
            return list;
        }

        private Sequence<T> RemoveItemAt(int index)
        {
            Node n = this as Node;
            int c = n.Left.Count;
            int t = index.CompareTo(c);
            if (t < 0)
            {
                Sequence<T> tl = n.Left.RemoveItemAt(index);
                return BalanceRight(tl, n.Item, n.Right);
            }
            else if (t > 0)
            {
                Sequence<T> tr = n.Right.RemoveItemAt(index - c - 1);
                return BalanceLeft(n.Left, n.Item, tr);
            }
            else
            {
                return Glue(n.Left, n.Right);
            }
        }

        public Sequence<T> RemoveAt(int index)
        {
            CheckProperListIndex(index, Count);
            return RemoveItemAt(index);
        }

        public Sequence<T> RemoveRangeAt(int index, int count)
        {
            CheckListRange(index, count, Count);
            if (count == 0)
                return this;
            Sequence<T> list = this;
            for (int i = 0; i < count; i++)
                list = list.RemoveAt(index);
            return list;
        }
        #endregion

        #region mutable list details
        private Sequence()
        {
        }
        #endregion

        #region readonly list details
        public int BinarySearch(T item)
        {
            return BinarySearch(item, default(IComparer<T>));
        }

        public int BinarySearch(T item, IComparer<T> comparer)
        {
            return BinarySearch(0, Count, item, comparer);
        }

        public int BinarySearch(T item, Comparison<T> comparison)
        {
            if (comparison == null)
                throw new ArgumentNullException(nameof(comparison));
            return BinarySearch(0, Count, item, comparison);
        }

        public int BinarySearch(int index, int count, T item, Comparison<T> comparison)
        {
            if (comparison == null)
                throw new ArgumentNullException(nameof(comparison));
            return BinarySearch(index, count, item, comparison.AsComparer());
        }

        public int BinarySearch(int index, int count, T item, IComparer<T> comparer)
        {
            CheckListRange(index, count, Count);
            comparer = comparer ?? Comparer<T>.Default;
            int i = index;
            int j = index + count - 1;
            while (i <= j)
            {
                int k = i + (j - i) / 2;
                int t = comparer.Compare(item, this[k]);
                if (t < 0)
                    j = k - 1;
                else if (t > 0)
                    i = k + 1;
                else
                    return k;
            }
            return ~i;
        }

        public bool Contains(T item)
        {
            if (item == null)
            {
                foreach (T value in this)
                    if (value == null)
                        return true;
            }
            else
            {
                var comparer = EqualityComparer<T>.Default;
                foreach (T value in this)
                    if (comparer.Equals(value, item))
                        return true;
            }
            return false;
        }

        private bool Contains(object item)
        {
            return IsItemCompatible(item) && Contains((T)item);
        }

        public Sequence<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter)
        {
            if (converter == null)
                throw new ArgumentNullException(nameof(converter));
            if (this is Leaf)
                return Sequence<TOutput>.Leaf.Instance;
            int index = 0;
            TOutput[] list = new TOutput[Count];
            foreach (T item in this)
                list[index++] = converter(item);
            return Sequence.New(list);
        }

        public void CopyTo(T[] array)
        {
            CheckTargetArray(array, 0, Count);
            CopyTo(array, 0);
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            CheckTargetArray(array, arrayIndex, Count);
            CopyTo(0, array, arrayIndex, Count);
        }

        public void CopyTo(int index, T[] array, int arrayIndex, int count)
        {
            CheckListRange(index, count, Count);
            CheckTargetArray(array, arrayIndex, count);
            int endIndex = index + count;
            for (int i = index; i < endIndex; i++)
                array[arrayIndex++] = this[i];
        }

        private void CopyTo(object[] array, int arrayIndex)
        {
            CheckTargetArray(array, arrayIndex, Count);
            foreach (T item in this)
                array[arrayIndex++] = item;
        }

        private void CopyTo(Array array, int arrayIndex)
        {
            CheckTargetArray(array, arrayIndex, Count);
            var itemArray = array as T[];
            if (itemArray != null)
            {
                CopyTo(itemArray, arrayIndex);
                return;
            }
            var objectArray = array as object[];
            if (objectArray != null)
            {
                try
                {
                    CopyTo(objectArray, arrayIndex);
                    return;
                }
                catch (ArrayTypeMismatchException)
                {
                    throw new ArgumentException(SR.InvalidArrayElementType, nameof(array));
                }
            }
            throw new ArgumentException(SR.InvalidArrayElementType, nameof(array));
        }

        public bool Exists(Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            foreach (T item in this)
                if (match(item))
                    return true;
            return false;
        }

        public T Find(Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            foreach (T item in this)
                if (match(item))
                    return item;
            return default(T);
        }

        public Sequence<T> FindAll(Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            List<T> list = new List<T>();
            foreach (T item in this)
                if (match(item))
                    list.Add(item);
            return Sequence.New(list);
        }

        public int FindIndex(Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            int i = 0;
            foreach (T item in this)
            {
                if (match(item))
                    return i;
                i++;
            }
            return -1;
        }

        public int FindIndex(int index, Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            CheckListIndex(index, Count);
            return FindIndex(index, Count - index, match);
        }

        public int FindIndex(int index, int count, Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            CheckListRange(index, count, Count);
            int endIndex = index + count;
            for (int i = index; i < endIndex; i++)
                if (match(this[i]))
                    return i;
            return -1;
        }

        public T FindLast(Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            for (int i = Count - 1; i > -1; i--)
            {
                T item = this[i];
                if (match(item))
                    return item;
            }
            return default(T);
        }

        public int FindLastIndex(Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            return FindLastIndex(Count - 1, Count, match);
        }

        public int FindLastIndex(int index, Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            return FindLastIndex(index, index + 1, match);
        }

        public int FindLastIndex(int index, int count, Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            CheckReverseListRange(index, count, Count);
            int endIndex = index - count;
            for (int i = index; i > endIndex; i--)
                if (match(this[i]))
                    return i;
            return -1;
        }

        public void ForEach(Action<T> action)
        {
            if (action == null)
                throw new ArgumentNullException(nameof(action));
            foreach (T item in this)
                action(item);
        }

        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        public Sequence<T> GetRange(int index, int count)
        {
            CheckListRange(index, count, Count);
            T[] list = new T[count];
            CopyTo(index, list, 0, count);
            return Sequence.New(list);
        }

        public int IndexOf(T item)
        {
            if (item == null)
            {
                int i = 0;
                foreach (T value in this)
                {
                    if (value == null)
                        return i;
                    i++;
                }
            }
            else
            {
                var comparer = EqualityComparer<T>.Default;
                int i = 0;
                foreach (T value in this)
                {
                    if (comparer.Equals(value, item))
                        return i;
                    i++;
                }
            }
            return -1;
        }

        public int IndexOf(T item, int index)
        {
            CheckListIndex(index, Count);
            return IndexOf(item, index, Count - index);
        }

        public int IndexOf(T item, int index, int count)
        {
            CheckListRange(index, count, Count);
            int endIndex = index + count;
            if (item == null)
            {
                for (int i = index; i < endIndex; i++)
                    if (this[i] == null)
                        return i;
            }
            else
            {
                var comparer = EqualityComparer<T>.Default;
                for (int i = index; i < endIndex; i++)
                    if (comparer.Equals(this[i], item))
                        return i;
            }
            return -1;
        }

        private int IndexOf(object item)
        {
            return IsItemCompatible(item) ? IndexOf((T)item) : -1;
        }

        public int LastIndexOf(T item)
        {
            return LastIndexOf(item, Count - 1);
        }

        public int LastIndexOf(T item, int index)
        {
            CheckReverseListIndex(index, Count);
            return LastIndexOf(item, index, index + 1);
        }

        public int LastIndexOf(T item, int index, int count)
        {
            CheckReverseListRange(index, count, Count);
            int endIndex = index - count;
            if (item == null)
            {
                for (int i = index; i > endIndex; i--)
                    if (this[i] == null)
                        return i;
            }
            else
            {
                var comparer = EqualityComparer<T>.Default;
                for (int i = index; i > endIndex; i--)
                    if (comparer.Equals(this[i], item))
                        return i;
            }
            return -1;
        }

        public T[] ToArray()
        {
            if (Count == 0)
                return ArrayExtensions.GetEmpty<T>();
            T[] array = new T[Count];
            CopyTo(array, 0);
            return array;
        }

        public override string ToString()
        {
            return "[" + string.Join(", ", this) + "]";
        }

        public bool TrueForAll(Predicate<T> match)
        {
            if (match == null)
                throw new ArgumentNullException(nameof(match));
            foreach (T item in this)
                if (!match(item))
                    return false;
            return true;
        }

        private bool IsFixedSize => true;
        private bool IsReadOnly => true;
        private bool IsSynchronized => false;

        private object SyncRoot
        {
            get
            {
                throw new InvalidOperationException(SR.ImmutableListOpUnsupported);
            }
        }

        public T this[int index]
        {
            get
            {
                CheckProperListIndex(index, Count);
                Node n = GetNode(index);
                return n.Item;
            }
            set
            {
                throw new NotSupportedException(SR.CollectionReadOnly);
            }
        }

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();

        void ICollection.CopyTo(Array array, int arrayIndex) => CopyTo(array, arrayIndex);
        int ICollection.Count => Count;
        bool ICollection.IsSynchronized => IsSynchronized;
        object ICollection.SyncRoot => SyncRoot;
        void ICollection<T>.Add(T item) { throw new InvalidOperationException(SR.CollectionReadOnly); }
        void ICollection<T>.Clear() { throw new InvalidOperationException(SR.CollectionReadOnly); }
        bool ICollection<T>.Contains(T item) => Contains(item);
        void ICollection<T>.CopyTo(T[] array, int arrayIndex) => CopyTo(array, arrayIndex);
        bool ICollection<T>.Remove(T item) { throw new InvalidOperationException(SR.CollectionReadOnly); }
        int ICollection<T>.Count => Count;
        bool ICollection<T>.IsReadOnly => IsReadOnly;
        int IReadOnlyCollection<T>.Count => Count;

        int IList.Add(object item) { throw new InvalidOperationException(SR.CollectionReadOnly); }
        void IList.Clear() { throw new InvalidOperationException(SR.CollectionReadOnly); }
        bool IList.Contains(object item) => Contains(item);
        int IList.IndexOf(object item) => IndexOf(item);
        void IList.Insert(int index, object item) { throw new InvalidOperationException(SR.CollectionReadOnly); }
        void IList.Remove(object item) { throw new InvalidOperationException(SR.CollectionReadOnly); }
        void IList.RemoveAt(int item) { throw new InvalidOperationException(SR.CollectionReadOnly); }
        bool IList.IsFixedSize => IsFixedSize;
        bool IList.IsReadOnly => IsReadOnly;
        int IList<T>.IndexOf(T item) => IndexOf(item);
        void IList<T>.Insert(int index, T item) => Insert(index, item);
        void IList<T>.RemoveAt(int index) { throw new InvalidOperationException(SR.CollectionReadOnly); }
        T IReadOnlyList<T>.this[int index] => this[index];

        object IList.this[int index]
        {
            get { return this[index]; }
            set { throw new InvalidOperationException(SR.CollectionReadOnly); }
        }

        T IList<T>.this[int index]
        {
            get { return this[index]; }
            set { throw new InvalidOperationException(SR.CollectionReadOnly); }
        }
        #endregion

        #region list comparison
        public int CompareTo(Sequence<T> other)
        {
            return IListExtensions.ListCompareTo(this, other);
        }

        public int CompareTo(object obj)
        {
            if (obj == null)
                return 1;
            if (obj is Sequence<T>)
                return CompareTo((Sequence<T>)obj);
            throw new ArgumentException(SR.ObjectsAreNotComparable);
        }

        public bool Equals(Sequence<T> other)
        {
            return IListExtensions.ListEquals(this, other);
        }

        public override bool Equals(object obj)
        {
            return obj is Sequence<T> && Equals((Sequence<T>)obj);
        }

        public override int GetHashCode()
        {
            return IListExtensions.GetListHashCode(this);
        }
        #endregion

        #region enumerator details
        [Serializable]
        public struct Enumerator : IEnumerator<T>
        {
            private readonly Sequence<T> _owner;
            private readonly Stack<Node> _stack;
            private Node _n;
            private int _index;

            public Enumerator(Sequence<T> owner)
            {
                if (owner == null)
                    throw new ArgumentNullException(nameof(owner));
                _owner = owner;
                _stack = new Stack<Node>();
                _n = owner as Node;
                _index = 0;
                _current = default(T);
            }

            private void Dispose()
            {
            }

            public bool MoveNext()
            {
                if (_index < _owner.Count)
                {
                    while (_n != null)
                    {
                        _stack.Push(_n);
                        _n = _n.Left as Node;
                    }
                    _n = _stack.Pop();
                    _current = _n.Item;
                    _n = _n.Right as Node;
                    _index++;
                    return true;
                }
                _n = null;
                _index = _owner.Count + 1;
                _current = default(T);
                return false;
            }

            private void Reset()
            {
                _stack.Clear();
                _n = _owner as Node;
                _index = 0;
                _current = default(T);
            }

            private T _current;
            public T Current
            {
                get
                {
                    CheckEnumeratorStatus(_index, _owner.Count);
                    return _current;
                }
            }

            void IDisposable.Dispose() => Dispose();
            bool IEnumerator.MoveNext() => MoveNext();
            void IEnumerator.Reset() => Reset();
            object IEnumerator.Current => Current;
            T IEnumerator<T>.Current => Current;
        }
        #endregion

        #region utility methods
        private static void CheckCollectionVersion(int originalVersion, int version)
        {
            if (originalVersion != version)
                throw new InvalidOperationException(SR.EnumFailedVersion);
        }

        private static void CheckEnumeratorStatus(int index, int size)
        {
            if (index == 0 || index == size + 1)
                throw new InvalidOperationException(SR.EnumOpCantHappen);
        }

        private static void CheckTargetArray(T[] array, int arrayIndex, int size)
        {
            if (array == null)
                throw new ArgumentNullException(nameof(array));
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException(nameof(arrayIndex), SR.IndexMustBeNonNegative);
            if (size < 0)
                throw new ArgumentOutOfRangeException(nameof(size), SR.SizeMustBeNonNegative);
            if (arrayIndex > array.Length)
                throw new ArgumentOutOfRangeException(nameof(arrayIndex), SR.IndexOutOfRange);
            if (size > array.Length - arrayIndex)
                throw new ArgumentException(SR.TargetArrayTooSmall, nameof(array));
        }

        private static void CheckTargetArray(Array array, int arrayIndex, int size)
        {
            if (array == null)
                throw new ArgumentNullException(nameof(array));
            if (array.Rank != 1)
                throw new ArgumentException(SR.RankMultiDimNotSupported, nameof(array));
            if (array.GetLowerBound(0) != 0)
                throw new ArgumentException(SR.NonZeroLowerBound, nameof(array));
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException(nameof(arrayIndex), SR.IndexMustBeNonNegative);
            if (size < 0)
                throw new ArgumentOutOfRangeException(nameof(size), SR.SizeMustBeNonNegative);
            if (arrayIndex > array.Length)
                throw new ArgumentOutOfRangeException(nameof(arrayIndex), SR.IndexOutOfRange);
            if (size > array.Length - arrayIndex)
                throw new ArgumentException(SR.TargetArrayTooSmall, nameof(array));
        }

        private static void CheckListIndex(int index, int size)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexMustBeNonNegative);
            if (size < 0)
                throw new ArgumentOutOfRangeException(nameof(size), SR.SizeMustBeNonNegative);
            if (index > size)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
        }

        private static void CheckProperListIndex(int index, int size)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexMustBeNonNegative);
            if (size < 0)
                throw new ArgumentOutOfRangeException(nameof(size), SR.SizeMustBeNonNegative);
            if (index >= size)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
        }

        private static void CheckReverseListIndex(int index, int size)
        {
            if (index < -1)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
            if (size < 0)
                throw new ArgumentOutOfRangeException(nameof(size), SR.SizeMustBeNonNegative);
            if (index >= size)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
        }

        private static void CheckListRange(int index, int count, int size)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexMustBeNonNegative);
            if (count < 0)
                throw new ArgumentOutOfRangeException(nameof(count), SR.CountMustBeNonNegative);
            if (size < 0)
                throw new ArgumentOutOfRangeException(nameof(size), SR.SizeMustBeNonNegative);
            if (index > size)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
            if (count > size - index)
                throw new ArgumentException(SR.InvalidIndexAndCount);
        }

        private static void CheckReverseListRange(int index, int count, int size)
        {
            if (index < -1)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
            if (count < 0)
                throw new ArgumentOutOfRangeException(nameof(index), SR.CountMustBeNonNegative);
            if (size < 0)
                throw new ArgumentOutOfRangeException(nameof(size), SR.SizeMustBeNonNegative);
            if (index >= size)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
            if (count > index + 1)
                throw new ArgumentException(SR.InvalidIndexAndCount);
        }

        private static void CheckItemCompatible(object item)
        {
            if (!IsItemCompatible(item))
            {
                string message = string.Format(SR.WrongCollectionElementType, nameof(item), typeof(T));
                throw new ArgumentException(message, nameof(item));
            }
        }

        private static bool IsItemCompatible(object item)
        {
            return IsObjectCompatible(item);
        }

        private static bool IsObjectCompatible(object obj)
        {
            return obj is T || obj == null && default(T) == null;
        }
        #endregion

        #region debug view
        private const string DebugDisplay = "Count = {Count}";

        [Serializable]
        private sealed class DebugView
        {
            private readonly Sequence<T> _collection;

            public DebugView(Sequence<T> collection)
            {
                if (collection == null)
                    throw new ArgumentNullException(nameof(collection));
                _collection = collection;
            }

            [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
            public T[] Items
            {
                get
                {
                    T[] array = new T[_collection.Count];
                    _collection.CopyTo(array, 0);
                    return array;
                }
            }
        }
        #endregion
    }

    public static class Sequence
    {
        public static Sequence<T> GetEmpty<T>()
        {
            return Sequence<T>.Leaf.Instance;
        }

        public static Sequence<T> New<T>(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException(nameof(collection));
            var c = collection as ICollection<T>;
            if (c != null && c.Count == 0)
                return GetEmpty<T>();
            return Sequence<T>.BuildTree(collection);
        }

        public static Sequence<T> Create<T>(params T[] items)
        {
            if (items == null)
                throw new ArgumentNullException(nameof(items));
            return New(items);
        }

        public static Sequence<T> Append<T>(Sequence<T> seq, T item)
        {
            if (seq == null)
                throw new ArgumentNullException(nameof(seq));
            return seq.Add(item);
        }

        public static Sequence<T> Prepend<T>(T item, Sequence<T> seq)
        {
            if (seq == null)
                throw new ArgumentNullException(nameof(seq));
            return seq.Insert(0, item);
        }

        public static Sequence<T> Concat<T>(Sequence<T> seq1, Sequence<T> seq2)
        {
            if (seq1 == null)
                throw new ArgumentNullException(nameof(seq1));
            if (seq2 == null)
                throw new ArgumentNullException(nameof(seq2));
            return seq1.Concat(seq2);
        }
    }
}
